package leetcode.code787.CheapestFlightsWithinKStops;

/**
 * dp超时
 *
 * @author Max
 * @date 2021年8月24日
 * @description
 */
public class Solution78703 extends CheapestFlightsWithinKStops {

	@Override
	public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
		boolean[] start = new boolean[n];
		boolean[] end = new boolean[n];
		Integer[][][] cache = new Integer[n][n][k + 1];
		final int MAX = 1000001;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int m = 0; m <= k; m++) {
					cache[i][j][m] = 1000001;
				}
			}
		}
		for (int[] flight2 : flights) {
			int[] flight = flight2;
			start[flight[0]] = true;
			end[flight[1]] = true;
			cache[flight[0]][flight[1]][0] = flight[2];
		}
		if (!start[src] || !end[dst]) {
			return -1;
		}
		if (k == 0) {
			return cache[src][dst][0] == MAX ? -1 : cache[src][dst][0];
		}
		Integer min = MAX;
		for (int m = 0; m <= k; m++) {
			if (m != 0) {
				for (int i = 0; i < n; i++) {
					if (start[i])
						for (int j = 0; j < n; j++) {
							if (end[j]) {
								Integer temp = MAX;
								for (int p = 0; p < n; p++) {
									if (start[p] && end[p]) {
										for (int q = 0; q <= k && m - q - 1 >= 0; q++) {
											int now = cache[i][p][q] + cache[p][j][m - q - 1];
											temp = Math.min(now, temp);
										}

									}
								}
								cache[i][j][m] = temp;
							}
						}
				}
			}
			min = Math.min(min, cache[src][dst][m]);
		}
		return min == MAX ? -1 : min;
	}

	public static void main(String[] args) {
		Solution78703 so = new Solution78703();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
